package com.math;


import java.util.Scanner;

public class Quick_sort {
    public static int N = 100010, n;
    public static int[] original_list = new int[N];
    public static void main(String[] args) {
        //输入
//        Scanner in = new Scanner(System.in);
//        n = in.nextInt();
//        for (int i = 0; i<n; i++) original_list[i] = in.nextInt();

        n = 5;
        int[] original_list = {3, 1, 2, 7, 5};

        quickSort(original_list, 0, n-1);   		//传入arr，起始位置，结束位置
        for (int i = 0; i<n; i++) System.out.print(original_list[i] + " ");
    }

    public static void quickSort(int[] numList, Integer left, Integer right) {
        if (left >= right) {return;}            //如果left大于等于right就直接返回了

        int x = numList[left];                  //设置一个分割数，这个数随便啦，一般用中间也就是(left+right)/2，我这里偷懒用left也不影响
        int i = left - 1;                       //开头指针，最开始设置为-1，不用担心, 因为有do while会++所以不会超过边界
        int j = right + 1;                      //末尾指针，最开始设置为5，同理
        while (i < j) {
            do i++; while (numList[i] < x);     //从头开始拿到大于等于x的值的下标
            do j--; while (numList[j] > x);     //从尾开始拿到小于等于x的值的下标
            if (i < j) {
                int temp = numList[i];          //if内做的是swap两个值的动作，吐槽下java没有swap吗
                numList[i] = numList[j];
                numList[j] = temp;
            }
        }

        quickSort(numList, left, j);            //将前半串递归
        quickSort(numList, j + 1, right);   	//将后半串递归
    }
}

